#include<iostream>
#include<vector>
using namespace std;
// 这个题目我这里使用动态规划来辅助完成这个题目
// 首先要解决这道题目的思路就是：我可以求出每一根柱子能够储存的雨水，然后将所有的答案加起来
// 如何求第i根柱子能够储存的雨水数量呢？如果left[i]代表的是i这个柱子左边所有柱子中最长的那个柱子
// right[i]就是i这个柱子右边的所有柱子中最长的那个柱子
// 那么此时i这个柱子能够储存的水分就是min(left[i],right[i]) - height[i]
// 然后将所有的柱子的这个值求出来，那么这道题目就解决了。下面要求的就是left[i]和right[i]了
// 这两个数组就是动态规划思想来求了
// left[i]代表从0到i这个柱子中最长的柱子的长度
// left[i] = max(left[i-1],height[i])
// 而right[i]代表从i到n-1的所有柱子中最长的柱子长度
// right[i]= max(right[i+1],height[i])
// 为什么都要将i这个柱子的长度带上呢？因为可能出现i这个位置的柱子比两边的柱子都长的情况，此时这个柱子能够保存的数量
// 应该是0而不应该是负数(如果不考虑i这个柱子就会导致负数的出现)
// 这道题目的动态规划只是一个辅助的手段，主要是思考出这个解法，动态规划只是一个辅助手段
class Solution {
public:
    int trap(vector<int>& height) {
        int ret = 0;//这是用来储存最多水分的变量
        //然后我要使用前缀和
        int  n = height.size();
        vector<int> left(n,0);
        left[0] = height[0];
        vector<int> right(n,0);
        for(int i = 1;i<n;i++)
        {
            left[i] = max(left[i-1],height[i]);
        }
        right[n-1] = height[n-1];
        for(int i = n-2;i>=0;i--)
        {
            right[i] = max(right[i+1],height[i]);
        }
        //然后就是去遍历然后进行计算了
        for(int i = 0;i<height.size();i++)
        {
            ret+=min(left[i],right[i])-height[i];
        }
        return ret;
    }
};